﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Data;
using System.Linq;
using System.Text;

namespace NSDecisionTree.DTree
{
    public class Tree
    {
        #region private 
        int numAttributes;
        string[] attributeNames;
        ArrayList[] domains;
        TreeNode root = new TreeNode();
        string retStr = String.Empty;
        #endregion

        #region public
        public string RetStr
        {
            get { return retStr; }
        }
        public ArrayList[] Domains
        {
            get { return domains; }
            set { domains = value; }
        }
        public int NumAttributes
        {
            get { return numAttributes; }
            set { numAttributes = value; }
        }
        public TreeNode Root
        {
            get { return root; }
        }
        public string[] AttributeNames
        {
            get { return attributeNames; }
            set { attributeNames = value; }
        }
        #endregion

        #region Functions
        private int GetSymbolValue(int Attribute, string Symbol)
        {
            int index = domains[Attribute].IndexOf(Symbol);
            if (index < 0)
            {
                domains[Attribute].Add(Symbol);
                return domains[Attribute].Count - 1;
            }
            return index;
        }

        public int[] GetAllValues(ArrayList Data, int Attribute)
        {
            ArrayList values = new ArrayList();
            int num = Data.Count;
            for (int i = 0; i < num; i++)
            {
                DataPoint dp = (DataPoint)Data[i];
                String symbol = (string)domains[Attribute][dp.Attributes[Attribute]];
                int index = values.IndexOf(symbol);
                if (index < 0)
                {
                    values.Add(symbol);
                }
            }

            int[] array = new int[values.Count];

            for (int i = 0; i < array.Length; i++)
            {
                String symbol = (string)values[i];
                array[i] = domains[Attribute].IndexOf(symbol);
            }
            values = null;
            return array;
        }

        public String[] GetAllStringValues(ArrayList Data, int Attribute)
        {
            ArrayList values = new ArrayList();
            int num = Data.Count;
            for (int i = 0; i < num; i++)
            {
                DataPoint dp = (DataPoint)Data[i];
                String symbol = (string)domains[Attribute][dp.Attributes[Attribute]];
                int index = values.IndexOf(symbol);
                if (index < 0)
                {
                    values.Add(symbol);
                }
            }

            int[] array = new int[values.Count];

            for (int i = 0; i < array.Length; i++)
            {
                String symbol = (string)values[i];
                array[i] = domains[Attribute].IndexOf(symbol);
            }

            return values.ToArray(typeof(string)) as string[];
        }

        private ArrayList GetSubset(ArrayList Data, int Attribute, int Value)
        {
            ArrayList retVal = new ArrayList();
            int num = Data.Count;

            for (int i = 0; i < num; i++)
            {
                DataPoint dp = (DataPoint)Data[i];
                if (dp.Attributes[Attribute] == Value)
                    retVal.Add(dp);
            }

            return retVal;
        }

        private double CalculateEntropy(ArrayList Data)
        {
            int numData = Data.Count;
            if (numData == 0)
                return 0;

            int attribute = numAttributes - 1;
            int numValues = domains[attribute].Count;
            double sum = 0;

            for (int i = 0; i < numValues; i++)
            {
                int count = 0;
                for (int j = 0; j < numData; j++)
                {
                    DataPoint dp = (DataPoint)Data[j];
                    if (dp.Attributes[attribute] == i)
                        count++;
                }
                double probability = (double)count/numData;
                if (count > 0)
                    sum += (double)(-1) * probability * System.Math.Log(probability, 2);
                        // (double)System.Math.Log(probability, 2);
            }
            return sum;
        }

        private bool AlreadyUsedToDecompose(TreeNode Node, int Attribute)
        {
            if (Node.Children != null)
            {
                if (Node.DecompositionAttribute == Attribute)
                    return true;
            }

            if (Node.Parent == null)
                return false;

            return AlreadyUsedToDecompose(Node.Parent, Attribute);
        }

        private void DecomposeNode(TreeNode Node, String RootNode)
        {
            double bestEntropy = 0;
            bool selected = false;
            int selectedAttribute = 0;

            int numData = Node.Data.Count;
            int numInputAttributes = numAttributes - 1;
            Node.Entropy = CalculateEntropy(Node.Data);

            if (Node.Entropy == 0)
                return;

            for (int i = 0; i < numInputAttributes; i++)
            {
                int numValues = domains[i].Count;
                if (AlreadyUsedToDecompose(Node, i))
                    continue;

                double averageEntropy = 0;

                for (int j = 0; j < numValues; j++)
                {
                    ArrayList subset = GetSubset(Node.Data, i, j);

                    if (subset.Count == 0)
                        continue;

                    double subEntropy = CalculateEntropy(subset);

                    averageEntropy += subEntropy * subset.Count;
                }

                averageEntropy = averageEntropy / numData;
                if (!String.IsNullOrEmpty(RootNode) && attributeNames[i] == RootNode)
                    averageEntropy = -1;

                if (selected == false)
                {
                    selected = true;
                    bestEntropy = averageEntropy;
                    selectedAttribute = i;
                    Node.Name = attributeNames[i];
                }
                else
                {
                    if (averageEntropy < bestEntropy)
                    {
                        selected = true;
                        bestEntropy = averageEntropy;
                        selectedAttribute = i;
                        Node.Name = attributeNames[i];
                    }
                }
            }

            if (selected == false)
                return;

            int numvalues = domains[selectedAttribute].Count;
            Node.DecompositionAttribute = selectedAttribute;
            Node.Children = new TreeNode[numvalues];

            for (int j = 0; j < numvalues; j++)
            {
                Node.Children[j] = new TreeNode();
                Node.Children[j].Parent = Node;
                Node.Children[j].Data = GetSubset(Node.Data, selectedAttribute, j);
                Node.Children[j].DecomositionValue = j;
            }

            for (int j = 0; j < numvalues; j++)
            {
                DecomposeNode(Node.Children[j], String.Empty);
            }

            Node.Data = null;
        }

        public void CreateDecisionTree()
        {
            DecomposeNode(root, String.Empty);
        }

        public void CreateDecisionTree(DataTable DT)
        {
            CreateDecisionTree(DT, String.Empty);
        }

        public void CreateDecisionTree(DataTable DT, String RootNode)
        {
            FillData(DT);
            DecomposeNode(root, RootNode);
        }

        private void FillData(DataTable DT)
        {
            numAttributes = DT.Columns.Count;
            domains = new ArrayList[numAttributes];
            attributeNames = new String[numAttributes];

            for (int i = 0; i < numAttributes; i++)
            {
                domains[i] = new ArrayList();
                attributeNames[i] = DT.Columns[i].Caption;
            }

            foreach (DataRow rowElement in DT.Rows)
            {
                object[] attributVals = rowElement.ItemArray;
                DataPoint point = new DataPoint(numAttributes);

                for (int i = 0; i < numAttributes; i++)
                {
                    point.Attributes[i] = GetSymbolValue(i, attributVals[i].ToString());
                }
                root.Data.Add(point);
            }

        }

        public string PrintTree(TreeNode Node, String tab, string retVal)
        {
            int outputAttr = numAttributes - 1;

            if (Node.Children == null)
            {
                int[] values = GetAllValues(Node.Data, outputAttr);
                if (values.Length == 1)
                {
                    retVal += tab + "\t" + attributeNames[outputAttr] + " = \"" + domains[outputAttr][values[0]] + "\";\r\n";
                    return retVal;
                }
                retVal += tab + "\t" + attributeNames[outputAttr] + " = {";
                for (int i = 0; i < values.Length; i++)
                {
                    retVal += "\"" + domains[outputAttr][values[i]] + "\"";
                    if (i != values.Length - 1)
                        retVal += " , ";
                }
                retVal += " };\r\n";
                return retVal;
            }

            int numValues = Node.Children.Length;
            for (int i = 0; i < numValues; i++)
            {
                retVal += tab + "if( " + attributeNames[Node.DecompositionAttribute] + " == \"" + domains[Node.DecompositionAttribute][i] + "\") {\r\n";
                retVal = PrintTree(Node.Children[i], tab + "\t", retVal);
                if (i != numValues - 1)
                    retVal += tab + "} else ";
                else
                    retVal += tab + "}\r\n";
            }

            return retVal;
        }

        public void printTree(TreeNode node, String tab)
        {
            int outputattr = numAttributes - 1;

            if (node.Children == null)
            {
                int[] values = GetAllValues(node.Data, outputattr);
                if (values.Length == 1)
                {
                    retStr += (tab + "\t" + attributeNames[outputattr] + " = \"" + domains[outputattr][values[0]] + "\";\r\n");
                    return;
                }

                retStr += (tab + "\t" + attributeNames[outputattr] + " = {");
                for (int i = 0; i < values.Length; i++)
                {
                    retStr += ("\"" + domains[outputattr][values[i]] + "\" ");
                    if (i != values.Length - 1)
                        retStr += (" , ");
                }
                retStr += (" };");
                return;
            }

            int numvalues = node.Children.Length;
            for (int i = 0; i < numvalues; i++)
            {
                retStr += (tab + "if( " + attributeNames[node.DecompositionAttribute] + " == \"" +
                        domains[node.DecompositionAttribute][i] + "\") {");
                printTree(node.Children[i], tab + "\t");
                if (i != numvalues - 1)
                    retStr += (tab + "} else ");
                else
                    retStr += (tab + "}");
            }
        }
        #endregion
    }
}
